1. Field of the Invention
The present invention relates to automated routing tools for integrated circuit designs.
2. Description of the Related Art
With the advent of circuit feature sizes in the sub-micron range, integrated circuits involving millions of transistors on a single chip have become commonplace. Due to the sheer number of devices on a single chip, an entire industry has evolved specifically to supply the semiconductor industry with software and hardware tools to automate much of the process of integrated circuit design.
Design automation tools are computer-based tools that assist through automation of procedures that would otherwise be performed manually. Simulation of proposed design functionality and synthesis of integrated circuit logic and layout are two examples. Design verification tools are computer-based tools used to verify that circuit design or layout meets certain prescribed objectives.
Both design automation and design verification tools require computer-readable descriptions of the underlying circuit function and structure to operate. These computer-based descriptions vary from simple geometrical specification languages, such as Caltech Intermediate Form (CIF) to high-level functional description languages such as VHDL (a hardware design language). Geometrical specification languages for integrated circuits allow computer-readable definition of the geometries of the mask layers required to fabricate an integrated circuit. These specification languages contain primitive structures such as wires and boxes to specify geometrical shapes and layout levels. Organizational constructs are also provided to allow placement and repetition of the geometrical structures.
Most design tools are hierarchical in nature and employ more than one type of routing algorithm for routing interconnections between circuit components. Most routing tools used for cell-based designs begin with the placement of circuit elements, cells and/or cell blocks. Placement can be manual or automated, and typically decisions are made about where connectors to the circuit elements, cells and/or cell blocks should be located. Placement also includes determining the placement and orientation of blocks relative to one another. Such decisions can be driven by considerations of circuit compaction, which affects circuit congestion (similar to traffic congestion), the number of interconnect lines running between the blocks, and so on. With gate array designs, there is no placement step because placement has been predetermined by the manufacturer.
The next step in completing the circuit design is typically a global routing step, which is an attempt to logically determine a path for each interconnection between cells in the entire design. Routing decisions are made based on the available avenues formed by the current placement of circuit elements and/or blocks, and are assigned in consideration of various costs, also referred to herein as constraints (e.g., to incur the shortest total length of interconnect lines between the connectors). Once the global router has assigned the general flow of interconnect lines, a detailed router attempts to make the interconnect lines fit the assignments made by the global router.
A set of two or more interconnected cells in a circuit design is referred to herein as a “net.” A “net list” is a set of statements in a geometrical specification language that specifies the elements of a circuit, such as transistors and gates, and their interconnections. Individual transistors are described, along with cells to which they connect. The net list allows creation of a circuit diagram based on the actual geometrical specification statements. The creation of the circuit diagram is referred to as “circuit extraction,” and the extracted circuit can be compared to the original circuit specified by the designer to determine differences. A difference usually indicates an error that must be corrected.
In addition to providing the details of circuit interconnection, circuit extraction is useful for calculating layout areas and perimeters for each integrated circuit layer at each node of the circuit. These layout areas and perimeters can be used to accurately calculate the parasitic capacitances and resistance that load the active devices. With accurate capacitances and resistances from circuit extraction, a design can be accurately simulated to ensure correct operation. Thus, circuit extraction is an essential design verification tool for accurate characterization of modern integrated circuits.
A typical analysis in designing a circuit involves developing a routing solution for routing interconnections between circuit components. The routing solution is then evaluated using a constraint engine to identify nets that do not meet specified criteria, such as minimum spacing between nets. Offending nets are manually re-routed, and the routing solution and constraint engine re-run. This process is referred to as “parasitic extraction.”
As more complicated designs are developed to achieve higher performance and higher reliability, the demands placed on routing tools increase. Most current routing tools, provided by Electronic Design Automation (EDA) vendors, are insufficient to achieve the quality of route desired without several iterations and design cycles. Furthermore, most routing tools are primarily concerned with minimal distance as a constraint on global routing and do not permit timing to be directly considered.
What is needed is a new global routing technique to achieve a high quality, highly reliable route in as few iterations as possible. The global router should provide the capability to handle timing, noise avoidance, shielding and cell (repeater or latch) insertion constraints. The global router should produce output that can be used by a commercially available detailed router to complete the routing.